package previous.Test_0204;

import java.util.List;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
class ListNode {
     int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
public class Solution {
    //汉若塔问题
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
          dfs(A,B,C, A.size());
    }
    public void dfs(List<Integer> a,List<Integer> b,List<Integer> c,int n){
        if(n==1){
            c.add(a.remove(a.size()-1));
            return;
        }
        dfs(a,c,b,n-1);
        c.add(a.remove(a.size()-1));
        dfs(b,a,c,n-1);
    }
    //反转链表
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode newHead=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }
    //合并两个有序链表
    ListNode head=new ListNode();
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1.next==null){
            return list2;
        }
           if( list2.next==null){
               return list1;
           }
           if(list1.val<= list2.val){
               list1.next=mergeTwoLists(list1.next,list2);
               return list1;
           }else {
               list2.next=mergeTwoLists(list1,list2.next);
               return list2;
           }

    }
    //快速幂
    public double myPow(double x, long n) {
          if(n>0){
              return Pow(x,n);
          }else{
              return 1.0/Pow(x,-n);
             }
    }
    public double Pow(double x,long n){
        if(n==0){
            return 1.0;
        }
        double tmp=Pow(x,n/2);
        if(n%2==1){
                return tmp*tmp*x;
            }
        return tmp*tmp;
    }
    //两两交换链表的节点
    public ListNode swapPairs(ListNode head) {
          if(head==null || head.next==null){
                return head;
          }
          ListNode tmp=swapPairs(head.next.next);
          ListNode newHead=head.next;
          head.next=head;
          head=tmp;
          return newHead;
    }
}
